﻿//#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//#include<vector>
//#include<unordered_map>
//#include<unordered_set>
//#include<string>
//#include<algorithm>
//#include<set>
//#include<map>
//using namespace std;
////class A
////{
////public:
////	void Print()
////	{
////		cout << "A::Print()" << endl;
////	}
////private:
////	int _a;
////};
////int main()
////{
////	A* p = nullptr;
////	p->Print();
////	return 0;
////}
////class A
////{
////public:
////	void Print()
////	{
////		cout << "A::Print()" << endl;
////		cout << _a << endl;
////	}
////private:
////	int _a;
////};
////int main()
////{
////	A* p = nullptr;
////	p->Print();
////	return 0;
////}
//// class Teacher : public Person
////{
////protected:
////	int _jobid; // 工号
////};
////class Person
////{
////public:
////	void Print()
////	{
////		cout << "name:" << _name << endl;
////		cout << "age:" << _age << endl;
////	}
////protected:
////	string _name = "peter"; // 姓名
////	int _age = 18;  // 年龄
////};
////class Student : public Person
////{
////protected:
////	int _stuid; // 学号
////};
////
//// void test()
////{
////	Student s;
////	Teacher t;
////	s.Print();
////	t.Print();
////	return 0;
////}
////class Person
////{
////protected:
////	string _name; // 姓名
////	string _sex;  // 性别
////	int _age;
////	// 年龄
////};
////class Student/*派生类*/ : public Person/*基类*/
////{
////public:
////	int _No; // 学号
////};
////void test()
////{
////	Student sobj;
////	Person pojb = sobj;
////	Person* pp = &sobj;
////	Person& rp = sobj;
////
////	//sobj = pojb;
////	pp = &sobj;
////}
////class A
////{
////public:
////	void fun()
////	{
////		cout << "func()" << endl;
////	}
////};
////class B : public A
////{
////public:
////	void fun(int i)
////	{
////		A::fun();
////		cout << "func(int i)->" << i << endl;
////	}
////};
////void Test()
////{
////	B b;
////	b.fun(10);
////};
////int main()
////{
////	Test();
////	return 0;
////}
////class Person
////{
////public:
////	Person(const char* name = "peter")
////		: _name(name)
////	{
////		cout << "Person()" << endl;
////	}
////	Person(const Person& p)
////		: _name(p._name)
////	{
////		cout << "Person(const Person& p)" << endl;
////	}
////	Person& operator=(const Person& p)
////	{
////		cout << "Person operator=(const Person& p)" << endl;
////		if (this != &p)
////			_name = p._name;
////		return *this;
////	}
////	~Person()
////	{
////		cout << "~Person()" << endl;
////	}
////protected:
////	string _name; // 姓名
////};
////class Student : public Person
////{
////public:
////	Student(const char* name, int num)
////		: Person(name)
////		, _num(num)
////	{
////		cout << "Student()" << endl;
////	}
////	Student(const Student& s)
////		: Person(s)
////		, _num(s._num)
////	{
////		cout << "Student(const Student& s)" << endl;
////	}
////	Student& operator = (const Student& s)
////	{
////		cout << "Student& operator= (const Student& s)" << endl;
////		if (this != &s)
////		{
////			Person::operator =(s);
////			_num = s._num;
////		}
////		return *this;
////	}
////	~Student()
////	{
////		cout << "~Student()" << endl;
////	}
////protected:
////	int _num; //学号
////};
////void Test()
////{
////	Student s1("jack", 18);
////	Student s2(s1);
////	Student s3("rose", 17);
////	s1 = s3;
////}
////int main()
////{
////	Test();
////	return 0;
////}
////class A
////{
////public:
////	virtual void func(int val = 1) { std::cout << "A->" << val << std::endl; }
////	virtual void test() { func(); }
////};
////class B : public A
////{
////public:
////	void func(int val = 0) { std::cout << "B->" << val << std::endl; }
////};
////int main(int argc, char* argv[])
////{
////	B* p = new B;
////	p->test();
////	return 0;
////}
//
////class person {
////public:
////	virtual void buyticket() { cout << "买票-全价" << endl; }
////};
////class student : public person {
////public:
////	virtual void buyticket() { cout << "买票-半价" << endl; }
////	/*注意：在重写基类虚函数时，派生类的虚函数在不加virtual关键字时，虽然也可以构成重写(因
////   为继承后基类的虚函数被继承下来了在派生类依旧保持虚函数属性),但是该种写法不是很规范，不建议
////   这样使用*/
////   /*void buyticket() { cout << "买票-半价" << endl; }*/
////};
////void func(person& p)
////{
////	p.buyticket();
////}
////int main()
////{
////	person ps;
////	student st;
////	func(ps);
////	func(st);
////	return 0;
////}
////
////class A {};
////class B : public A {};
////class Person {
////public:
////	virtual A* f() { return new A; }
////};
////class Student : public Person {
////public:
////	virtual B* f() { return new B; }
////};
////void Func(Person* ptr)
////{
////	ptr->f()
////}
////int main()
////{
////
////	return 0;
////}
////class A
////{
////public:
////    A() : m_iVal(0) 
////    { 
////        test(); 
////    }
////    virtual void func()
////    { 
////        std::cout << m_iVal << " "; 
////    }
////  void test() 
////  {
////      func(); 
////  }
////public:
//// int m_iVal;
////};
////class B : public A
////{
////public:
////    B() 
////    { 
////        test(); 
////    }
////    virtual void func()
////    {
////        ++m_iVal;
////        std::cout << m_iVal <<" ";
////    }
////};
////int main(int argc, char* argv[])
////{
////    A* p = new B;
////    p->test();
////    return 0;
////}
////int getrand(vector<int>& nums, int left, int right)
////{
////    int r = rand();
////    return nums[r % (right - left + 1) + left];
////}
////void qsort(vector<int>& nums, int l, int r)
////{
////    if (l >= r) return;
////
////    int key = getrand(nums, l, r);
////    int i = l, left = l - 1, right = r + 1;
////    while (i < right)
////    {
////        if (nums[i] == key) i++;
////        else if (nums[i] < key) swap(nums[++left], nums[i++]);
////        else swap(nums[--right], nums[i]);
////    }
////    qsort(nums, l, left);
////    qsort(nums, right, r);
////}
////vector<int> sortArray(vector<int>& nums) {
////    srand(time(NULL));
////    qsort(nums, 0, nums.size() - 1);
////    return nums;
////}
////
////int main()
////{
////    vector<int> nums = { 5,1,1,2,0,0 };
////    sortArray(nums);
////    return 0;
////}
//
//
//
//
////int getrand(vector<int>& nums, int left, int right)
////{
////    return nums[rand() % (right - left + 1) + left];
////}
////void qsort(vector<int>nums, int l, int r, int k)
////{
////    if (l >= r) return;
////    int key = getrand(nums, l, r);
////    int right = r + 1, left = l - 1, i = l;
////
////    while (i < right)
////    {
////        if (nums[i] < key) swap(nums[++left], nums[i++]);
////        else if (nums[i] == key) i++;
////        else swap(nums[--right], nums[i]);
////    }
////
////    int a = left - l + 1, b = right - left;
////    if (a > k) qsort(nums, l, left, k);
////    else if (a + b >= k) return;
////    else qsort(nums, right, r, k - a - b);
////}
////vector<int> inventoryManagement(vector<int>& nums, int k) {
////    srand(time(NULL));
////    qsort(nums, 0, nums.size() - 1, k);
////    return { nums.begin(),nums.begin() + k };
////}
////
////int main()
////{
////    vector<int> nums = { 0,0,1,2,4,2,2,3,1,4 };
////    inventoryManagement(nums,8);
////    return 0;
////}
//
// 
//
////int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
////    int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
////    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
////    dp[0][1] = 1;
////    for (int i = 1; i <= m; i++)//从上往下遍历每一行
////    {
////        for (int j = 1; j <= n; j++)//从左往右遍历每一行
////        {
////            if (obstacleGrid[i - 1][j - 1] == 1)
////                dp[i][j] = 0;
////            else
////                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
////        }
////    }
////    return dp[m][n];
////}
////int main()
////{
////    int m = 3, n = 2;
////    vector<vector<int>> dp={ {0,0} };
////    uniquePathsWithObstacles(dp);
////	return 0;
//
////int main()
////{
////	int left = 0, right = 7;
////	int mid = (left + right) >> 1;
////	printf("%d ", mid);
////	mid = mid >> 1;
////	printf("%d ", mid);
////	return 0;
////}
//
////class Person
////{
////public:
////	virtual void BuyTicket()
////	{
////		cout << "买票全价" << endl;
////	}
////};
////class Student : public Person
////{
////public:
////	virtual void BuyTicket()
////	{
////		cout << "买票半价" << endl;
////	}
////};
////void Func(Person & ptr)
////{
////	ptr.BuyTicket();
////}
////void Test()
////{
////	Person person;
////	Func(person);
////
////	Student johnson;
////	Func(johnson);
////}
////int main()
////{
////	Test();
////	return 0;
////}
//
////class A
////{
////public:
////	virtual ~A()
////	{
////		cout << "~A()" << endl;
////	}
////};
////class B : public A {
////public:
////	~B()
////	{
////		cout << "~B()->delete:" << _p << endl;
////		delete _p;
////	}
////protected:
////	int* _p = new int[10];
////};
////
////int main()
////{
////	A* p1 = new A;
////	A* p2 = new B;
////
////	delete p1;
////	delete p2;
////	return 0;
////}
//
////class Car
////{
////public:
////	virtual void Drive() = 0;
////};
////
////class Benz :public Car
////{
////public:
////	virtual void Drive()
////	{
////		cout << "Benz舒适" << endl;
////	}
////};
////
////class BMW :public Car
////{
////public:
////	virtual void Drive()
////	{
////		cout << "BMW操控" << endl;
////	}
////};
//// 
////int main()
////{
////	Car* pBenz = new Benz;
////	pBenz->Drive();
////
////	Car* pBMW = new BMW;
////	pBMW->Drive();
////	
////	return 0;
////}
//
////int main()
////{
//	//set<int, greater<int>> s;
//	//set<int>s;
//
//	//s.insert(5);
//	//s.insert(2);
//	//s.insert(7);
//	//s.insert(5);
//	//auto it = s.begin();
//	//while (it != s.end())
//	//{
//	//	cout << *it << " ";
//	//	++it;
//	//}
//	//cout << endl;
//
//	//s.insert({ 2,8,3,9 });
//	//for (auto e : s)
//	//{
//	//	cout << e << " ";
//	//}
//	//cout << endl;
//
//	//set<string> strset = { "sort","insert","add" };
//	//for (auto& e : strset)
//	//{
//	//	cout << e << " ";
//	//}
//	//cout << endl;
//
//	//set<int> s = { 4,2,7,2,8,5,9 };
//	//for (auto e : s)
//	//{
//	//	cout << e << " ";
//	//}
//	//cout << endl;
//	//s.erase(s.begin());
//	//for (auto e : s)
//	//{
//	//	cout << e << " ";
//	//}
//	//int x;
//	//cin >> x;
//	//int num = s.erase(x);
//	//if(num == 0)
//	//{
//	//	cout << x << "不存在！" << endl;
//	//}
//	//for (auto e : s)
//	//{
//	//	cout << e << " ";
//	//}
//	//cout << endl;
////
////	auto pos1 = find(s.begin(), s.end(), x);
////	auto pos2 = s.find(x);
////	cin >> x;
////	if (s.count(x))
////	{
////		cout << x << "在！" << endl;
////	}
////	else
////	{
////		cout << x << "不存在！" << endl;
////	}
////
////	return 0;
////}
//
////int main()
////{
////	set<int> myset;
////	for (int i = 0; i < 10; i++)
////	{
////		myset.insert(i * 10);
////	} 
////	for (auto e : myset)
////	{
////		cout << e << " ";
////	}
////	cout << endl;
////
////	auto itlow = myset.lower_bound(30);
////	auto itup = myset.upper_bound(60);
////
////	myset.erase(itlow, itup);
////	for (auto e : myset)
////	{
////		cout << e << " ";
////	}
////	cout << endl;
////	return 0;
////}
//
////int main()
////{
////	const size_t N = 100000;
////
////	unordered_set <int> us;
////	set<int> s;
////
////	vector<int> v;
////	v.reserve(N);
////	srand(time(0));
////	for (size_t i = 0; i < N; ++i)
////	{
////		v.push_back(rand() + i);
////	}
////
////	size_t begin1 = clock();
////	for (auto e : v)
////	{
////		s.insert(e);
////	}
////	size_t end1 = clock();
////	cout << "set insert:" << end1 - begin1 << endl;
////
////	size_t begin2 = clock();
////	us.reserve(N);
////	for (auto e : v)
////	{
////		us.insert(e);
////	}
////	size_t end2 = clock();
////	cout << "unordered_set insert:" << end2 - begin2 << endl;
////
////	int m1 = 0;
////	size_t begin3 = clock();
////	for (auto e : v)
////	{
////		auto ret = s.find(e);
////		if (ret != s.end())
////		{
////			++m1;
////		}
////	}
////	size_t end3 = clock();
////	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
////
////	int m2 = 0;
////	size_t begin4 = clock();
////	for (auto e : v)
////	{
////		auto ret = us.find(e);
////		if (ret != us.end())
////		{
////			++m2;
////		}
////	}
////
////	size_t end4 = clock();
////	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
////	cout << "插入数据个数：" << s.size() << endl;
////	cout << "插入数据个数：" << us.size() << endl << endl;
////	size_t begin5 = clock();
////	for (auto e : v)
////	{
////		s.erase(e);
////	}
////	size_t end5 = clock();
////	cout << "set erase:" << end5 - begin5 << endl;
////	size_t begin6 = clock();
////	for (auto e : v)
////	{
////		us.erase(e);
////	}
////	size_t end6 = clock();
////	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
////	return 0;
////}
////struct Point
////{
////	int _x;
////	int _y;
////};
////class Date
////{
////public:
////	Date(int year = 1, int month = 1, int day = 1)
////		:_year(year)
////		, _month(month)
////		, _day(day)
////	{
////		cout << "Date(int year, int month, int day)" << endl;
////	}
////
////	Date(const Date& d)
////		:_year(d._year)
////		, _month(d._month)
////		, _day(d._day)
////	{
////		cout << "Date(const Date& d)" << endl;
////	}
////private:
////	int _year;
////	int _month;
////	int _day;
////};
////int main()
////{
////	const Date& d2 = { 2024, 7, 25 };
////	Date d1 = { 2024, 7, 25 };
////	return 0;
////}
//
////};
////int add(int x, int y)
////{
////	int z = 0;
////	z = x + y;
////	return z;
////}
////int main()
////{
////	/*string ret = Solution().addStrings("1111111111111111111", "22222222222222222222");
////	cout << ret << endl;*/
////	int ret2 = add(1, 2);
////	printf("%d", ret2);
////	return 0;
////}
//
////int main()
////{
////	// 左值：可以取地址
////	// 以下的p、b、c、* p、s、s[0]就是常见的左值
////
////	int* p = new int(0);
////	int b = 1;
////	const int c = b;
////	*p = 10;
////	string s("111111");
////	s[0] = 'x';
////	double x = 1.1, y = 2.2;
////
////	// 左值引?给左值取别名
////	int& r1 = b;
////	int*& r2 = p;
////	int& r3 = *p;
////	string& r4 = s;
////	char& r5 = s[0];
////
////	// 右值引?给右值取别名
////	int&& rr1 = 10;
////	double&& rr2 = x + y;
////	double&& rr3 = fmin(x, y);
////	string&& rr4 = string("11111");
////
////	// 左值引?不能直接引?右值，但是const左值引?可以引?右值
////	const int& rx1 = 10;
////	const double& rx2 = x + y;
////	const double& rx3 = fmin(x, y);
////	const string& rx4 = string("11111");
////
////	// 右值引?不能直接引?左值，但是右值引?可以引?move(左值)
////	int&& rrx1 = move(b);
////	int*&& rrx2 = move(p);
////	int&& rrx3 = move(*p);
////	string&& rrx4 = move(s);
////	string&& rrx5 = (string&&)s;
////
////	// b、r1、rr1都是变量表达式，都是左值
////	cout << &b << endl;
////	cout << &r1 << endl;
////	cout << &rr1 << endl;
////
////	// 这?要注意的是，rr1的属性是左值，所以不能再被右值引?绑定，除?move?下
////	int& r6 = rr1;
////	// int&& rrx6 = rr1;
////	int&& rrx6 = move(rr1);
////	return 0;
////}
////
////void f(int& x)
////{
////	cout << "左值引?重载f(" << x << ") \n";
////}
////void f(const int& x)
////{
////	cout << "到const的左值引?重载f(" << x << ") \n";
////}
////void f(int&& x)
////{
////	cout << "右值引?重载f(" << x << ")\n";
////}
////int main()
////{
////	int i = 1;
////	const int ci = 2;
////	f(i);  // 调?f(int&)
////	f(ci); // 调?f(const int&)
////	f(3);  // 调?f(int&&)，如果没有f(int&&)重载则会调?f(const int&)
////	f(std::move(i)); // 调?f(int&&)
////	// 右值引?变量在?于表达式时是左值
////
////	int&& x = 1;
////	f(x);            // 调?f(int& x)
////	f(std::move(x)); // 调?f(int&& x)
////	return 0;
////}
////namespace bit
////{
////	class string
////	{
////	public:
////		typedef char* iterator;
////		typedef const char* const_iterator;
////
////		iterator begin()
////		{
////			return _str;
////		}
////
////		iterator end()
////		{
////			return _str + _size;
////		}
////
////		const_iterator begin() const
////		{
////			return _str;
////		}
////
////		const_iterator end() const
////		{
////			return _str + _size;
////		}
////
////		string(const char* str = "")
////			:_size(strlen(str))
////			, _capacity(_size)
////		{
////			cout << "string(char* str)-构造" << endl;
////			_str = new char[_capacity + 1];
////			strcpy(_str, str);
////		}
////
////		// 拷贝构造
////		string(const string& s)
////			:_str(nullptr)
////		{
////			cout << "string(const string& s) -- 拷贝构造" << endl;
////			reserve(s._capacity);
////			for (auto ch : s)
////			{
////				push_back(ch);
////			}
////		}
////
////		void swap(string& ss)
////		{
////			::swap(_str, ss._str);
////			::swap(_size, ss._size);
////			::swap(_capacity, ss._capacity);
////		}
////
////		// 移动构造
////		string(string&& s)
////		{
////			cout << "string(string&& s) -- 移动构造" << endl;
////			// 转移掠夺你的资源
////			swap(s);
////		}
////
////		string& operator=(const string& s)
////		{
////			cout << "string& operator=(const string& s) -- 拷贝赋值" <<
////				endl;
////			if (this != &s)
////			{
////				_str[0] = '\0';
////				_size = 0;
////				reserve(s._capacity);
////				for (auto ch : s)
////				{
////					push_back(ch);
////				}
////			}
////			return *this;
////		}
////
////		// 移动赋值
////		string& operator=(string&& s)
////		{
////			cout << "string& operator=(string&& s) -- 移动赋值" << endl;
////			swap(s);
////			return *this;
////		}
////
////		~string()
////		{
////			//cout << "~string() -- 析构" << endl;
////			delete[] _str;
////			_str = nullptr;
////		}
////
////		char& operator[](size_t pos)
////		{
////			return _str[pos];
////		}
////
////		void reserve(size_t n)
////		{
////			if (n > _capacity)
////			{
////				char* tmp = new char[n + 1];
////				if (_str)
////				{
////					strcpy(tmp, _str);
////					delete[] _str;
////				}
////				_str = tmp;
////				_capacity = n;
////			}
////		}
////
////		void push_back(char ch)
////		{
////			if (_size >= _capacity)
////			{
////				size_t newcapacity = _capacity == 0 ? 4 : _capacity *
////					2;
////				reserve(newcapacity);
////			}
////			_str[_size] = ch;
////			++_size;
////			_str[_size] = '\0';
////		}
////
////		string& operator+=(char ch)
////		{
////			push_back(ch);
////			return *this;
////		}
////
////		const char* c_str() const
////		{
////			return _str;
////		}
////
////		size_t size() const
////		{
////			return _size;
////		}
////	private:
////		char* _str = nullptr;
////		size_t _size = 0;
////		size_t _capacity = 0;
////	};
////}
////
////class Solution {
////public:
////	// 传值返回需要拷贝
////	bit::string addStrings(bit::string num1, bit::string num2) {
////		bit::string str;
////		int end1 = num1.size() - 1, end2 = num2.size() - 1;
////		// 进位
////		int next = 0;
////		while (end1 >= 0 || end2 >= 0)
////		{
////			int val1 = end1 >= 0 ? num1[end1--] - '0' : 0;
////			int val2 = end2 >= 0 ? num2[end2--] - '0' : 0;
////			int ret = val1 + val2 + next;
////			next = ret / 10;
////			ret = ret % 10;
////			str += ('0' + ret);
////		}
////		if (next == 1)
////			str += '1';
////		reverse(str.begin(), str.end());
////		//cout << &str << endl;
////
////		return str;
////	}
////};
////int main()
////{
////	bit::string ret;
////	// ...
////
////	ret = Solution().addStrings("11111111111111111111", "222222222222222222222222222");
////	cout << ret.c_str() << endl;
////	//cout << &ret<< endl;
////
////	return 0;
////}
//
////int main()
////{
////	//bit::string ret = Solution().addStrings("11111111111111111111", "222222222222222222222222222");
////	//cout << ret << endl;
////
////	bit::string s1("11111111111111111");
////
////	bit::string s3 = s1;
////	bit::string s4 = bit::string("222222222");
////	bit::string s5 = move(s1);
////
////	return 0;
////}
////int main()
////{
////	typedef int& lref;
////	typedef int&& rref;
////	int n = 0;
////
////	lref& r1 = n;  // r1 的类型是int&
////	lref&& r2 = n; // r2 的类型是int&
////	rref& r3 = n;  // r3 的类型是int&
////	rref&& r4 = 1; // r4 的类型是int&&
////}
////class MyClass {
////public:
////	static int staticVar;
////};
////
//// 类外初始化
////int MyClass::staticVar = 10;
////class QQ {
////private:
////	int _val;
////
////public:
////	QQ(int val) 
////		: _val(val)
////	{}
////
////	// 声明QQFriend类为友元
////	friend class QQFriend;
////};
////class QQFriend {
////public:
////	void display(const QQ& obj)
////	{
////		// 可以访问 MyClass 的私有成员
////		cout << "Private _val: " << obj._val << endl;
////	}
////};
////
////
////class OuterClass {
////private:
////	int _OuterVal;
////
////public:
////	OuterClass(int val) : _OuterVal(val) {}
////
////	// 内部类定义
////	//默认InnerClass为OuterClass的友元类
////	class InnerClass {
////	private:
////		int _innerVal;
////
////	public:
////		InnerClass(int val) : _innerVal(val) {}
////
////		void display(const OuterClass& O) {
////			cout << "Inner class variable: " << _innerVal << endl;
////			cout << "Outer class variable: " << O._OuterVal << endl;
////		}
////	};
////
////	void displayOuter() {
////		cout << "Outer class variable: " << _OuterVal << endl;
////	}
////};
////#include <iostream>
////using namespace std;
////
////class QQ {
////public:
////	QQ() { cout << "Constructor called\n"; }
////	~QQ() { cout << "Destructor called\n"; }
////};
////
////int main() {
////	// 创建匿名对象并直接调用它的构造函数
////	QQ();
////	// 程序结束时会调用匿名对象的析构函数
////	return 0;
////}
////class QQ {
////public:
////	QQ(int value) { cout << "QQ(int value) " << value << endl; }
////	~QQ() { cout << "~QQ\n"; }
////};
////
////void func(QQ obj) {
////	cout << "func(QQ obj)\n";
////}
////
////int main() {
////	func(QQ(10));  // 创建一个匿名对象并传递给函数
////	return 0;
////}
////#include <iostream>
////using namespace std;
////
////class QQ {
////public:
////	QQ() 
////	{ 
////		cout << "QQ()\n"; 
////	}
////
////	~QQ()
////	{
////		cout << "~QQ()\n";
////	}
////};
////
////QQ createObject() {
////	return QQ();  // 返回一个匿名对象
////}
////
////int main() {
////	QQ obj = createObject();  // 接收匿名对象
////	return 0;
////}
////class QQ
////{
////public:
////	QQ(int a = 0)
////		:_a1(a)
////	{
////		cout << "QQ(int a = 0) —>直接构造" << endl;
////	}
////	QQ(const QQ& aa)
////		:_a1(aa._a1)
////	{
////		cout << "QQ(const QQ& aa) —>拷贝构造" << endl;
////	}
////	QQ& operator=(const QQ& aa)
////	{
////		cout << "QQ& operator=(const QQ& aa) —>赋值构造" << endl;
////		if (this != &aa)
////		{
////			_a1 = aa._a1;
////		}
////		return *this;
////	}
////	~QQ()
////	{
////		cout << "~QQ() —>析构" << endl;
////	}
////private:
////	int _a1 = 1;
////};
////void f1(QQ aa)
////{}
////QQ f2()
////{
////	QQ qq;
////	return qq;
////}
////
////int main()
////{
////	f1(QQ(2));
////
////	return 0;
////}
////int main()
////{
////	// 传值传参
////	// 构造+拷贝构造
////	//QQ qq1;
////	//f1(aa1);
////	//cout << endl;
////
////	// 隐式类型，连续构造+拷贝构造->优化为直接构造
////	//f1(1);
////
////	// ⼀个表达式中，连续构造 + 拷贝构造-> 优化为⼀个构造
////
////
////	f1(QQ(2));
////	// cout << endl;
////
////	//cout << "***********************************************" << endl;
////
////	// 传值返回 
////	// 不优化的情况下传值返回，编译器会⽣成⼀个拷贝返回对象的临时对象作为函数调⽤表达式的返回值 
////
////	// 无优化 （ vs2019 debug ） 
////	// ⼀些编译器会优化得更厉害，将构造的局部对象和拷贝构造的临时对象优化为直接构造（ vs2022 debug ）
////	//f2();
////	//cout << endl;
////
////	// 返回时⼀个表达式中，连续拷贝构造 + 拷贝构造-> 优化⼀个拷贝构造 （ vs2019 debug ）
////	// ⼀些编译器会优化得更厉害，进⾏跨⾏合并优化，
////	// 将构造的局部对象 aa 和拷贝的临时对象和接收返回值对象 aa2 优化为⼀个直接构造。（ vs2022 debug ）
////	//QQ qq2 = f2();
////	//cout << endl;
////
////	//qq1 = f2();
////	//cout << endl;
////
////	return 0;
////}
////int main()
////{
////	auto add1 = [](int x, int y)->int {return x + y; };
////	cout << add1(1, 2) << endl;
////
////	auto func1 = []
////		{
////			cout << "hello world" << endl;
////			return 0;
////		};
////	func1();
////
////	int a = 0, b = 1;
////	auto swap = [](int& x, int& y)
////		{
////			int tmp = x;
////			x = y;
////			y = x;
////		};
////	swap(a, b);
////	cout << a << ":" << b << endl;
////
////	return 0;
////}
//
////int x = 0;
////// 捕捉列表必须为空，因为全局变量不⽤捕捉就可以⽤，没有可被捕捉的变量
////
////auto func1 = []()
////	{
////		x++;
////	};
////int main()
////{
////	int a = 0, b = 1, c = 2, d = 3;
////	auto func1 = [a, &b]
////		{
////			b++;
////			int ret = a + b;
////			return ret;
////		};
////	cout << func1() << endl;
////
////	auto func2 = [=]
////		{
////			int ret = a + b + c;
////			return ret;
////		};
////	cout << func2() << endl;
////
////	auto func3 = [&]
////		{
////			a++;
////			c++;
////			d++;
////		};
////	func3();
////	cout << a << " " << b << " " << c << " " << d << endl;
////
////	//混合捕捉1
////		auto func4 = [&, a, b]
////		{
////			//a++;
////			//b++;
////			c++;
////			d++;
////			return a + b + c + d;
////		};
////		func4();
////		cout << a << " " << b << " " << c << " " << d << endl;
////
////		auto func5 = [=, &a, &b]
////			{
////				a++;
////				b++;
////				return a + b + c + d;
////			};
////		func5();
////		cout << a << " " << b << " " << c << " " << d << endl;
////
////		static int m = 0; static int m = 0;
////		auto func6 = []
////			{
////				int ret = x + m;
////				return ret;
////			};
////	return 0;
////}
//
////int main()
////{
////	int x = 10, y = 20;
////	auto func5 = [=,&x]()
////	{
////		cout << x << y << endl;
////	};
////	
////	return 0;
////}
//
////class QQ {
////public:
////	int x = 10;
////	void show() {
////		auto func7 = [this]() 
////			{ 
////				std::cout << "x = " << x << std::endl; 
////			};  // 捕获 this 指针
////		func7();
////	}
////};
////
////int main() {
////	QQ obj;
////	obj.show();  // 输出 "x = 10"
////	return 0;
////}
////
////int main()
////{
////	//捕获为空不能省略
////	//参数为空可以省略
////	//放回值可以省略，auto自动推到
////	//函数体不能省略
////	auto print = []
////		{
////			cout << "hello bit" << endl;
////			return 0;
////		};
////}
//double Divide(int a, int b)
//{
//	// 当b == 0时抛出异常
//
//	if (b == 0)
//	{
//		throw "Divide by zero condition!";
//	}
//	else
//	{
//		return (double)a / (double)b;
//	}
//}
//void Func()
//{
//	// 这⾥可以看到如果发⽣除0错误抛出异常，另外下⾯的array和array2没有得到释放。
//
//	// 所以这⾥捕获异常后并不处理异常，异常还是交给外⾯处理，这⾥捕获了再重新抛出去。
//
//	// 但是如果array2new的时候抛异常呢，就还需要套⼀层捕获释放逻辑，这⾥更好解决⽅案
//
//	// 是智能指针，否则代码太戳了
//
//	int* array1 = new int[10];
//	int* array2 = new int[10];   //抛异常呢
//
//	try
//	{
//		int len, time;
//		cin >> len >> time;
//		cout << Divide(len, time) << endl;
//	}
//	catch (...)
//	{
//		cout << "delete []" << array1 << endl;
//		cout << "delete []" << array2 << endl;
//#include<thread>
//		// ⼀般⼤型项⽬程序才会使⽤异常，下⾯我们模拟设计⼀个服务的⼏个模块
//
//		// 每个模块的继承都是Exception的派⽣类，每个模块可以添加⾃⼰的数据
//
//		// 最后捕获时，我们捕获基类就可以
//	}
//}
//int main()
//{
//	Func();
//	return 0;
//}
////class Exception
////{
////public:
////	Exception(const string& errmsg, int id)
////		:_errmsg(errmsg)
////		, _id(id)
////	{}
////	virtual string what() const
////	{
////		return _errmsg;
////	}
////	int getid() const
////	{
////		return _id;
////	}
////protected:
////	string _errmsg;
////	int _id;
////};
////class SqlException : public Exception
////{
////public:
////	SqlException(const string& errmsg, int id, const string& sql)
////		:Exception(errmsg, id)
////		, _sql(sql)
////	{}
////	virtual string what() const
////	{
////		string str = "SqlException:";
////		str += _errmsg;
////		str += "->";
////		str += _sql;
////		return str;
////	}
////private:
////	const string _sql;
////};
////class CacheException : public Exception
////{
////public:
////	CacheException(const string& errmsg, int id)
////		:Exception(errmsg, id)
////	{}
////	virtual string what() const
////	{
////		string str = "CacheException:";
////		str += _errmsg;
////		return str;
////	}
////};
////class HttpException : public Exception
////{
////public:
////	HttpException(const string& errmsg, int id, const string& type)
////		:Exception(errmsg, id)
////		, _type(type)
////	{}
////	virtual string what() const
////	{
////		string str = "HttpException:";
////		str += _type;
////		str += ":";
////		str += _errmsg;
////		return str;
////	}
////private:
////	const string _type;
////};
////void SQLMgr()
////{
////	if (rand() % 7 == 0)
////	{
////		throw SqlException("权限不⾜", 100, "select * from name = '张三'");
////	}
////	else
////	{
////		cout << "SQLMgr 调⽤成功" << endl;
////	}
////}
////void CacheMgr()
////{
////	if (rand() % 5 == 0)
////	{
////		throw CacheException("权限不⾜", 100);
////	}
////	else if (rand() % 6 == 0)
////	{
////		throw CacheException("数据不存在", 101);
////	}
////	else
////	{
////		cout << "CacheMgr 调⽤成功" << endl;
////	}
////	SQLMgr();
////}
////void HttpServer()
////{
////	if (rand() % 3 == 0)
////	{
////		throw HttpException("请求资源不存在", 100, "get");
////	}
////	else if (rand() % 4 == 0)
////	{
////		throw HttpException("权限不⾜", 101, "post");
////	}
////	else
////	{
////		cout << "HttpServer调⽤成功" << endl;
////	}
////	CacheMgr();
////}
////int main()
////{
////	srand(time(0));
////	while (1)
////	{
////		this_thread::sleep_for(chrono::seconds(1));
////		try
////		{
////			HttpServer();
////		}
////		catch (const Exception& e) // 这⾥捕获基类，基类对象和派⽣类对象都可以被捕获
////
////		{
////				cout << e.what() << endl;
////		}
////			catch (...)
////		{
////			cout << "Unkown Exception" << endl;
////		}
////	}
////	return 0;
////}
//

#include<iostream>
#include<list>
#include<vector>
#include<queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
void order(TreeNode* root, vector<vector<int>>& ret, int depth)
{
    if (root == nullptr) return;
    int size = depth;
    if (size == depth) ret.push_back(vector<int>());
        ret[depth].push_back(root->val);
    order(root->left, ret, depth + 1);
    order(root->right, ret, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    order(root, ret, 0);
    return ret;
}
int main()
{
    TreeNode* root4 = new TreeNode(15);
    TreeNode* root5 = new TreeNode(7);
    TreeNode* root2 = new TreeNode(9);
    TreeNode* root3 = new TreeNode(20,root4,root5);
    TreeNode* root = new TreeNode(3,root2,root3);

    levelOrder(root);
    return 0;
}